|
In the mathematical subfield of graph theory a level structure of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex.〔.〕 ==Definition and construction== Given a connected graph ''G'' = (''V'', ''E'') with ''V'' the set of vertices and ''E'' the set of edges, and with a root vertex ''r'', the level structure is a partition of the vertices into subsets ''Li'' called levels, consisting of the vertices at distance ''i'' from ''r''. Equivalently, this set may be defined by setting ''L''0 = , and then, for ''i'' > 0, defining ''Li'' to be the set of vertices that are neighbors to vertices in ''L''''i'' − 1 but are not themselves in any earlier level.〔 The level structure of a graph can be computed by a variant of breadth first search: algorithm level-BFS(G, r): Q ← for ℓ from 0 to ∞: process(Q, ℓ) ''// the set Q holds all vertices at level ℓ'' mark all vertices in Q as discovered Q' ← {} for u in Q: for each edge (u, v): if v is not yet marked: add v to Q' if Q' is empty: return Q ← Q' 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「level structure」の詳細全文を読む スポンサード リンク
|